import java.util.ArrayDeque;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-12
 * Time: 22:20
 */
public class Solution {
    public int getLCA(int a, int b) {
        // write code here
        ArrayDeque<Integer> queue1 = new ArrayDeque<>();
        ArrayDeque<Integer> queue2 = new ArrayDeque<>();
        // 编号从 1 开始, l = p * 2, r = p * 2 + 1
        while (a > 0) {
            queue1.add(a);
            a /= 2;
        }

        while (b > 0) {
            queue2.add(b);
            b /= 2;
        }

        if (queue1.size() > queue2.size()) {
            while (queue1.size() > queue2.size()) {
                queue1.pollFirst();
            }
        } else {
            while (queue2.size() > queue1.size()) {
                queue2.pollFirst();
            }
        }
//         注意这里面是包装类 Integer, 注意使用 equals 进行判断相等
//         使用 == 判断结果不对
        while (!queue1.getFirst().equals(queue2.getFirst())) {
            queue1.pollFirst();
            queue2.pollFirst();
        }
        return queue1.getFirst();
    }
}
